package cn.mayday.algorithms.year2020.month12;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
 * 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 * <p>
 * 示例 1：
 * <p>
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Mayday05
 * @date 2020/12/30 13:39
 */
public class Off03FindRepeatNumber {

    /**
     * 它考察的是程序员的沟通能力，先问面试官要时间/空间需求！！！
     * 只是时间优先就用字典，
     * 还有空间要求，就用指针+原地排序数组，
     * 如果面试官要求空间O(1)并且不能修改原数组，还得写成二分法！！！
     */
    public static void main(String[] args) {

        int[] test1 = {2, 3, 1, 0, 2, 5, 3};
        int result1 = new Off03FindRepeatNumber().findRepeatNumber(test1);

        System.out.println("result1 = " + result1);
    }

    // 方法1： 直接使用hash表 存储是否出现过 复杂度 O(N) 空间 O(N)
/*    public int findRepeatNumber(int[] nums) {
        // set
        Set alreadySet = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            if (alreadySet.contains(nums[i])) {
                return nums[i];
            }
            alreadySet.add(nums[i]);
        }
        return -1;
    }*/

    // 方法2： 排序 看前后元素是否相等 O(NlogN) 空间 O(1)
/*    public int findRepeatNumber(int[] nums) {

        return -1;
    }*/

    // 方法3：鸽巢原理，
    // 因为出现的元素值 < nums.size(); 所以我们可以将见到的元素 放到索引的位置，如果交换时，发现索引处已存在该元素，则重复 O(N) 空间O(1)

    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int value1 = nums[i]; // 当前循环数组

            // 一直交换
            while (value1 != i) {
                int value2 = nums[value1]; // 对应循环数值应该存在位置存在的数值
                // 数值
                if (value1 == value2) {
                    return value1;
                } else {
                    // 交换
                    nums[i] = value2;
                    nums[value1] = value1;
                }
            }
        }
        return -1;
    }

}
